class Solution {
    private TrieNode root;
    
    public static class TrieNode {
        String str;
        Map<Character, TrieNode> child;
        public TrieNode() {
            this.str = null;
            this.child = new HashMap<>();
        }
    }

    public String longestCommonPrefix(String[] strs) {
        root = new TrieNode();
        for (String str : strs) addWord(str);
        TrieNode node = root;
        StringBuilder sb = new StringBuilder();
        while (node.child.size() == 1) {
            if (node.str != null) return node.str;
            char ch = node.child.keySet().stream().findFirst().get();
            sb.append(ch);
            node = node.child.get(ch);
        }
        return sb.toString();
    }

    private void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.child.get(word.charAt(i)) == null) {
                node.child.put(word.charAt(i), new TrieNode());
            }
            node = node.child.get(word.charAt(i));
        }
        node.str = word;
    }
}
